package com.kevinkk.backtracking;

import java.util.ArrayList;
import java.util.List;

/**
 * 给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
 */

public class LetterCombinationsOfAPhoneNumber {
    class Solution {
        String[] map = {"", "", "abc", "def",
                "ghi", "jkl", "mno",
                "pqrs", "tuv", "wxyz"};
        List<String> res = new ArrayList<>();
        StringBuilder sb = new StringBuilder();

        public List<String> letterCombinations(String digits) {
            if(digits.isEmpty()) return res;
            backtracking(digits, 0);
            return res;
        }

        // 递归函数的参数：这道题不需要进行去重，直接用 index 来控制递归的深度
        private void backtracking(String digits, int index){
            if(index == digits.length()){
                res.add(sb.toString());
                return;
            }

            int number = digits.charAt(index) - '0';
            String letters = map[number];
            // 每一层只能在对应数字的字母表里进行选择
            for(int i = 0; i < letters.length(); i++){
                sb.append(letters.charAt(i));
                backtracking(digits, index+1);
                sb.deleteCharAt(sb.length()-1);
            }
        }
    }
}
